
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/35.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">题解 P4500 【[ZJOI2018]树】</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/生成函数/" class="tag"><span  style="background-color: rgb(231, 76, 60);">生成函数</span></a>&nbsp;<a href="/tags/题解/" class="tag"><span  style="background-color: rgb(82, 196, 26);">题解</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <h2 id="_1">题意</h2>
<p><input value="在洛谷上查看" type="button" onclick="creat('https://www.luogu.com.cn/problem/P4500')" class="btn btn-link"/></p>
<p>求随机生成 <script type="math/tex">k</script> 棵大小为 <script type="math/tex">n</script> 的有标号树互相有根同构的概率。</p>
<h2 id="_2">题解</h2>
<p>国际计<strong>树</strong>最高水平.jpg ，吉司机yyds<img alt="se" src="/img/62244.png">。</p>
<p>记录一下看到哪里了 <img alt="kl" src="/img/62226.png">。</p>
<p><del>最近在看 <script type="math/tex">\rm Analytic\ Combinatorics</script> 就使用那本书里面的命名规则罢。</del></p>
<p>越写越丑还是通篇抄复读罢。</p>
<p>记 <script type="math/tex">\mathcal T</script> 为一般无根树的集合，<script type="math/tex">\tau\in\mathcal T</script>，<script type="math/tex">|t|</script> 为树的节点数目。</p>
<p>记 <script type="math/tex">w(\tau)</script> 为给 <script type="math/tex">\tau</script> 标号的方案数，我们的目的是求出：
<script type="math/tex; mode=display">\sum_{\tau\in\mathcal T}w^k(\tau)</script>
先可以得到两个玩意儿拼接起来得到什么：
<script type="math/tex; mode=display">w((\tau_1,\tau_2))=w(\tau_1)w(\tau_2)\binom{|\tau_1|+|\tau_2|}{|\tau_1|,|\tau_2|}</script>
于是就很自然地写出 <script type="math/tex">\mathbf{GF}</script>：
<script type="math/tex; mode=display">\boxed{\color{orange}{T(\mathcal A;x)=\sum_{a\in\mathcal A}\frac{w^k(a)x^{|a|}}{(a!)^k}}}</script>
不难验证 <script type="math/tex">T(\mathcal A;x)\times T(\mathcal B;x)</script> 就是 <script type="math/tex">\mathcal A</script> 与 <script type="math/tex">\mathcal B</script> 的笛卡尔积的生成函数。</p>
<p>无根树构成的无序列表加上根应该就是无根树，因此：
<script type="math/tex; mode=display">\mathcal T=\text{root}\times\mathrm{MSET}(\mathcal T)</script>
遗憾的是，那本书上讲了 <script type="math/tex">\rm unlabelled</script> 的 <script type="math/tex">\mathrm{MSET}</script>，讲了 <script type="math/tex">\rm labelled</script> 的 <script type="math/tex">\mathrm{SET}</script>，可没有讲 <script type="math/tex">\rm labelled</script> 的 <script type="math/tex">\mathrm{MSET}</script>。（其实讲了也没有用，因为我们自己定义了笛卡尔积）</p>
<p>我们希望把组合运算转换成喜闻乐见的代数运算。</p>
<p>先是 <script type="math/tex">\mathrm{MSET}</script> 的问题。</p>
<p>回忆 <script type="math/tex">\mathbf{OGF}</script> 中有一个 <script type="math/tex">\mathrm{MSET}</script> 是长这样的：
<script type="math/tex; mode=display">\prod_{a\in A}\sum_{i=0}^\infty x^{i|a|}</script>
简单来说就是枚举每个元素选了多少个。</p>
<p>于是现在的 <script type="math/tex">\mathrm{MSET}</script> 也容易得到了。
<script type="math/tex; mode=display">\prod_{\tau\in \mathcal T}\sum_{i=0}^\infty\frac{\color{orange}w^{ik}(\tau)\color{noo}x^{i|\tau|}}{\color{orange}(|\tau|!)^{ik}(i!)^k}</script>
由于这 <script type="math/tex">i</script> 个无法区分，所以还要除以 <script type="math/tex">(i!)^k</script>。</p>
<p>如果我们引入 <script type="math/tex">\operatorname{xepx}</script> 为 <script type="math/tex">\displaystyle\sum_{i=0}^\infty \frac{x^i}{(i!)^k}</script>，于是就可把 <script type="math/tex">\mathrm{MSET}</script> 写成比较优美的形式：
<script type="math/tex; mode=display">\prod_{\tau\in\mathcal T}\operatorname{xexp} \frac{w^k(\tau)x^{|\tau|}}{(\tau!)^k}</script>
由于后面那一坨可以看做 <script type="math/tex">\tau</script> 的 <script type="math/tex">\mathbf{GF}</script>
<del>（连 <script type="math/tex">\tau</script> 都有gf了我还没有</del>
<script type="math/tex; mode=display">\prod_{\tau\in\mathcal T}\operatorname{xexp}\color{orange} T(\tau;x)</script>
<script type="math/tex">\operatorname{xexp} x</script>当 <script type="math/tex">k=0</script> 时就是 <script type="math/tex">\frac1{1-x}</script>，<script type="math/tex">k=1</script> 时就是普通的 <script type="math/tex">\exp</script>，很巧的是一点用都没有。</p>
<p>那么我们就使用 <script type="math/tex">\ln-\exp</script> 吧 积<script type="math/tex">\prod</script> 化 和 <script type="math/tex">\sum</script>。
<script type="math/tex; mode=display">\exp\left(\sum_{\tau\in\mathcal T}\ln\circ\operatorname{xexp}T(\tau;x)\right)</script>
如果令：
<script type="math/tex; mode=display">F(x)=\ln\circ\operatorname{xexp} x=\sum_{i\ge1}f_ix^i</script>
那么：
<script type="math/tex; mode=display">\ln\circ\operatorname{xexp}T(\tau;x)=F(T(\tau;x))</script>
于是：
<script type="math/tex; mode=display">
\begin{aligned}
\sum_{\tau\in\mathcal T}\ln\circ\operatorname{xexp} T(\tau;x)&=\sum_{\tau\in T}\sum_{i\ge1}f_iT(\tau;x)^i\\
&=\sum_{i\ge1}f_i\left(\sum_{\tau\in\mathcal T}T(\tau;x)^i\right)
\end{aligned}
</script>
好像就化不下去了。我们希望的是把 <script type="math/tex">T(\mathcal T;x)</script> 当成一个整体来操作，而不是枚举每一个元素使复杂度上天↑</p>
<p>所以还是老老实实把后面的拆开来：
<script type="math/tex; mode=display">=\sum_{\tau\in\mathcal T}\left(\frac{w^{ik}(\tau)x^{i|\tau|}}{(|\tau|!)^{ik}}\right)</script>
我们看到 <script type="math/tex">w(\tau)</script> 与 <script type="math/tex">|\tau|!</script> 的指数都是一样的，那么就可以考虑写成封闭形式。</p>
<p>如果记 
<script type="math/tex; mode=display">T(\mathcal T;x,a)=\sum_{\tau\in\mathcal T}\frac{w^a(\tau)x^{|\tau|}}{(|\tau|!)^a}</script>
那么上式就等于 <script type="math/tex">T(\mathcal T;x^i,ik)</script>。</p>
<p>
<script type="math/tex; mode=display">\exp\sum_{i\ge 1}f_i T(\mathcal T;x^i,ik)</script>
</p>
<p>然后现在是一个无序列表，我们希望给其加根。现在给它添加一个根，由于根的标号最小不会使 <script type="math/tex">w</script> 改变，因此这个 <em>积分</em> 就是：
<script type="math/tex; mode=display">\int:x^n\mapsto \frac{x^{n+1}}{(n+1)^k}</script>
那么就有：
<script type="math/tex; mode=display">T(\mathcal T;x,k)=\int\exp\sum_{i\ge1}f_iT(\mathcal T;x^i,ik)</script>
发现式中 <script type="math/tex">i</script> 最大的有用的值就是 <script type="math/tex">n</script>。因为大于 <script type="math/tex">n</script> 次的直接截断。并且 <script type="math/tex">T(\mathcal T;x^i,ik)</script> 只需要知道前 <script type="math/tex">\left\lfloor\dfrac ni\right\rfloor</script> 次就足够了。</p>
<h2 id="_3">代码</h2>
<div class="highlight"><pre><span></span><code><span class="linenos" data-linenos=" 1 "></span><span class="cp">#include</span><span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp"></span>
<span class="linenos" data-linenos=" 2 "></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="linenos" data-linenos=" 3 "></span><span class="kt">int</span> <span class="n">mod</span><span class="p">;</span>
<span class="linenos" data-linenos=" 4 "></span><span class="k">struct</span> <span class="nc">modint</span><span class="p">{</span>
<span class="linenos" data-linenos=" 5 "></span>    <span class="kt">int</span> <span class="n">x</span><span class="p">;</span>
<span class="linenos" data-linenos=" 6 "></span>    <span class="n">modint</span><span class="p">(</span><span class="kt">int</span> <span class="n">o</span><span class="o">=</span><span class="mi">0</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="n">o</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 7 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">=</span> <span class="p">(</span><span class="kt">int</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="n">x</span><span class="o">=</span><span class="n">o</span><span class="p">,</span><span class="o">*</span><span class="k">this</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 8 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">+=</span><span class="p">(</span><span class="n">modint</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="n">x</span><span class="o">=</span><span class="n">x</span><span class="o">+</span><span class="n">o</span><span class="p">.</span><span class="n">x</span><span class="o">&gt;=</span><span class="n">mod</span><span class="o">?</span><span class="n">x</span><span class="o">+</span><span class="n">o</span><span class="p">.</span><span class="n">x</span><span class="o">-</span><span class="nl">mod</span><span class="p">:</span><span class="n">x</span><span class="o">+</span><span class="n">o</span><span class="p">.</span><span class="n">x</span><span class="p">,</span><span class="o">*</span><span class="k">this</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 9 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">-=</span><span class="p">(</span><span class="n">modint</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="n">x</span><span class="o">=</span><span class="n">x</span><span class="o">-</span><span class="n">o</span><span class="p">.</span><span class="n">x</span><span class="o">&lt;</span><span class="mi">0</span><span class="o">?</span><span class="n">x</span><span class="o">-</span><span class="n">o</span><span class="p">.</span><span class="n">x</span><span class="o">+</span><span class="nl">mod</span><span class="p">:</span><span class="n">x</span><span class="o">-</span><span class="n">o</span><span class="p">.</span><span class="n">x</span><span class="p">,</span><span class="o">*</span><span class="k">this</span><span class="p">;}</span>
<span class="linenos" data-linenos="10 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">*=</span><span class="p">(</span><span class="n">modint</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="n">x</span><span class="o">=</span><span class="mf">1l</span><span class="n">l</span><span class="o">*</span><span class="n">x</span><span class="o">*</span><span class="n">o</span><span class="p">.</span><span class="n">x</span><span class="o">%</span><span class="n">mod</span><span class="p">,</span><span class="o">*</span><span class="k">this</span><span class="p">;}</span>
<span class="linenos" data-linenos="11 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">^=</span><span class="p">(</span><span class="kt">int</span> <span class="n">b</span><span class="p">){</span>
<span class="linenos" data-linenos="12 "></span>        <span class="n">modint</span> <span class="n">a</span><span class="o">=*</span><span class="k">this</span><span class="p">,</span><span class="n">c</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span>
<span class="linenos" data-linenos="13 "></span>        <span class="k">for</span><span class="p">(;</span><span class="n">b</span><span class="p">;</span><span class="n">b</span><span class="o">&gt;&gt;=</span><span class="mi">1</span><span class="p">,</span><span class="n">a</span><span class="o">*=</span><span class="n">a</span><span class="p">)</span><span class="k">if</span><span class="p">(</span><span class="n">b</span><span class="o">&amp;</span><span class="mi">1</span><span class="p">)</span><span class="n">c</span><span class="o">*=</span><span class="n">a</span><span class="p">;</span>
<span class="linenos" data-linenos="14 "></span>        <span class="k">return</span> <span class="n">x</span><span class="o">=</span><span class="n">c</span><span class="p">.</span><span class="n">x</span><span class="p">,</span><span class="o">*</span><span class="k">this</span><span class="p">;</span>
<span class="linenos" data-linenos="15 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos="16 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">/=</span><span class="p">(</span><span class="n">modint</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="o">*</span><span class="k">this</span> <span class="o">*=</span><span class="n">o</span><span class="o">^=</span><span class="n">mod</span><span class="mi">-2</span><span class="p">;}</span>
<span class="linenos" data-linenos="17 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">+=</span><span class="p">(</span><span class="kt">int</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="n">x</span><span class="o">=</span><span class="n">x</span><span class="o">+</span><span class="n">o</span><span class="o">&gt;=</span><span class="n">mod</span><span class="o">?</span><span class="n">x</span><span class="o">+</span><span class="n">o</span><span class="o">-</span><span class="nl">mod</span><span class="p">:</span><span class="n">x</span><span class="o">+</span><span class="n">o</span><span class="p">,</span><span class="o">*</span><span class="k">this</span><span class="p">;}</span>
<span class="linenos" data-linenos="18 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">-=</span><span class="p">(</span><span class="kt">int</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="n">x</span><span class="o">=</span><span class="n">x</span><span class="o">-</span><span class="n">o</span><span class="o">&lt;</span><span class="mi">0</span><span class="o">?</span><span class="n">x</span><span class="o">-</span><span class="n">o</span><span class="o">+</span><span class="nl">mod</span><span class="p">:</span><span class="n">x</span><span class="o">-</span><span class="n">o</span><span class="p">,</span><span class="o">*</span><span class="k">this</span><span class="p">;}</span>
<span class="linenos" data-linenos="19 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">*=</span><span class="p">(</span><span class="kt">int</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="n">x</span><span class="o">=</span><span class="mf">1l</span><span class="n">l</span><span class="o">*</span><span class="n">x</span><span class="o">*</span><span class="n">o</span><span class="o">%</span><span class="n">mod</span><span class="p">,</span><span class="o">*</span><span class="k">this</span><span class="p">;}</span>
<span class="linenos" data-linenos="20 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span> <span class="o">/=</span><span class="p">(</span><span class="kt">int</span> <span class="n">o</span><span class="p">){</span><span class="k">return</span> <span class="o">*</span><span class="k">this</span> <span class="o">*=</span> <span class="p">((</span><span class="n">modint</span><span class="p">(</span><span class="n">o</span><span class="p">))</span><span class="o">^=</span><span class="n">mod</span><span class="mi">-2</span><span class="p">);}</span>
<span class="linenos" data-linenos="21 "></span>    <span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">I</span><span class="o">&gt;</span><span class="k">friend</span> <span class="n">modint</span> <span class="k">operator</span> <span class="o">+</span><span class="p">(</span><span class="n">modint</span> <span class="n">a</span><span class="p">,</span><span class="n">I</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="o">+=</span><span class="n">b</span><span class="p">;}</span>
<span class="linenos" data-linenos="22 "></span>    <span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">I</span><span class="o">&gt;</span><span class="k">friend</span> <span class="n">modint</span> <span class="k">operator</span> <span class="o">-</span><span class="p">(</span><span class="n">modint</span> <span class="n">a</span><span class="p">,</span><span class="n">I</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="o">-=</span><span class="n">b</span><span class="p">;}</span>
<span class="linenos" data-linenos="23 "></span>    <span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">I</span><span class="o">&gt;</span><span class="k">friend</span> <span class="n">modint</span> <span class="k">operator</span> <span class="o">*</span><span class="p">(</span><span class="n">modint</span> <span class="n">a</span><span class="p">,</span><span class="n">I</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="o">*=</span><span class="n">b</span><span class="p">;}</span>
<span class="linenos" data-linenos="24 "></span>    <span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">I</span><span class="o">&gt;</span><span class="k">friend</span> <span class="n">modint</span> <span class="k">operator</span> <span class="o">/</span><span class="p">(</span><span class="n">modint</span> <span class="n">a</span><span class="p">,</span><span class="n">I</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="o">/=</span><span class="n">b</span><span class="p">;}</span>
<span class="linenos" data-linenos="25 "></span>    <span class="k">friend</span> <span class="n">modint</span> <span class="k">operator</span> <span class="o">^</span><span class="p">(</span><span class="n">modint</span> <span class="n">a</span><span class="p">,</span><span class="kt">int</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="o">^=</span><span class="n">b</span><span class="p">;}</span>
<span class="linenos" data-linenos="26 "></span>    <span class="k">friend</span> <span class="kt">bool</span> <span class="k">operator</span> <span class="o">==</span><span class="p">(</span><span class="n">modint</span> <span class="n">a</span><span class="p">,</span><span class="kt">int</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span><span class="o">==</span><span class="n">b</span><span class="p">;}</span>
<span class="linenos" data-linenos="27 "></span>    <span class="k">friend</span> <span class="kt">bool</span> <span class="k">operator</span> <span class="o">!=</span><span class="p">(</span><span class="n">modint</span> <span class="n">a</span><span class="p">,</span><span class="kt">int</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span><span class="o">!=</span><span class="n">b</span><span class="p">;}</span>
<span class="linenos" data-linenos="28 "></span>    <span class="kt">bool</span> <span class="k">operator</span> <span class="o">!</span> <span class="p">()</span> <span class="p">{</span><span class="k">return</span> <span class="o">!</span><span class="n">x</span><span class="p">;}</span>
<span class="linenos" data-linenos="29 "></span>    <span class="n">modint</span> <span class="k">operator</span> <span class="o">-</span> <span class="p">()</span> <span class="p">{</span><span class="k">return</span> <span class="n">x</span><span class="o">?</span><span class="n">mod</span><span class="o">-</span><span class="nl">x</span><span class="p">:</span><span class="mi">0</span><span class="p">;}</span>
<span class="linenos" data-linenos="30 "></span>    <span class="n">modint</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">++</span><span class="p">(</span><span class="kt">int</span><span class="p">){</span><span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="o">+=</span><span class="mi">1</span><span class="p">;}</span>
<span class="linenos" data-linenos="31 "></span><span class="p">};</span>
<span class="linenos" data-linenos="32 "></span><span class="k">const</span> <span class="kt">int</span> <span class="n">N</span><span class="o">=</span><span class="mf">2e3</span><span class="o">+</span><span class="mi">10</span><span class="p">;</span>
<span class="linenos" data-linenos="33 "></span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span><span class="n">k</span><span class="p">;</span>
<span class="linenos" data-linenos="34 "></span><span class="n">modint</span> <span class="n">inv</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">fac</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">ifac</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">pw</span><span class="p">[</span><span class="n">N</span><span class="p">][</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="35 "></span><span class="n">modint</span> <span class="n">g</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">f</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="36 "></span><span class="n">modint</span> <span class="n">c</span><span class="p">[</span><span class="n">N</span><span class="p">][</span><span class="n">N</span><span class="p">],</span><span class="n">t</span><span class="p">[</span><span class="n">N</span><span class="p">][</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="37 "></span><span class="kt">int</span> <span class="n">ans</span><span class="p">;</span>
<span class="linenos" data-linenos="38 "></span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="n">factors</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="39 "></span><span class="kt">signed</span> <span class="nf">main</span><span class="p">(){</span>
<span class="linenos" data-linenos="40 "></span>    <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d%d%d&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">n</span><span class="p">,</span><span class="o">&amp;</span><span class="n">k</span><span class="p">,</span><span class="o">&amp;</span><span class="n">mod</span><span class="p">);</span>
<span class="linenos" data-linenos="41 "></span>    <span class="n">inv</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">inv</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">modint</span><span class="p">(</span><span class="n">mod</span><span class="o">-</span><span class="n">mod</span><span class="o">/</span><span class="n">i</span><span class="p">)</span><span class="o">*</span><span class="n">inv</span><span class="p">[</span><span class="n">mod</span><span class="o">%</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="42 "></span>    <span class="n">fac</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="n">ifac</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">fac</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">fac</span><span class="p">[</span><span class="n">i</span><span class="mi">-1</span><span class="p">]</span><span class="o">*</span><span class="n">i</span><span class="p">,</span><span class="n">ifac</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">ifac</span><span class="p">[</span><span class="n">i</span><span class="mi">-1</span><span class="p">]</span><span class="o">*</span><span class="n">inv</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="43 "></span>    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">pw</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">modint</span><span class="p">(</span><span class="n">i</span><span class="p">)</span><span class="o">^</span><span class="n">k</span><span class="p">;</span>
<span class="linenos" data-linenos="44 "></span>    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span><span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="45 "></span>        <span class="n">pw</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">pw</span><span class="p">[</span><span class="n">j</span><span class="mi">-1</span><span class="p">][</span><span class="n">i</span><span class="p">]</span><span class="o">*</span><span class="n">pw</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="46 "></span>    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="47 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">*</span><span class="n">j</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="48 "></span>            <span class="n">factors</span><span class="p">[</span><span class="n">i</span><span class="o">*</span><span class="n">j</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
<span class="linenos" data-linenos="49 "></span>    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">m</span><span class="o">=</span><span class="n">n</span><span class="p">;</span><span class="n">m</span><span class="p">;</span><span class="n">m</span><span class="o">--</span><span class="p">){</span>
<span class="linenos" data-linenos="50 "></span>        <span class="n">g</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">/</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="p">(</span><span class="n">ifac</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">^</span><span class="mf">1l</span><span class="n">l</span><span class="o">*</span><span class="n">m</span><span class="o">*</span><span class="n">k</span><span class="o">%</span><span class="p">(</span><span class="n">mod</span><span class="mi">-1</span><span class="p">));</span>
<span class="linenos" data-linenos="51 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">/</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="52 "></span>            <span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">i</span><span class="o">*</span><span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="53 "></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;=</span><span class="n">i</span><span class="mi">-1</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="54 "></span>                <span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-=</span><span class="n">j</span><span class="o">*</span><span class="n">f</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">*</span><span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="p">];</span>
<span class="linenos" data-linenos="55 "></span>            <span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">*=</span><span class="n">inv</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="56 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos="57 "></span>        <span class="c1">//F(x)=ln(exp(x))</span>
<span class="linenos" data-linenos="58 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">/</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="59 "></span>            <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="nl">j</span><span class="p">:</span><span class="n">factors</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
<span class="linenos" data-linenos="60 "></span>                <span class="n">c</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">i</span><span class="p">]</span><span class="o">+=</span><span class="n">f</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">*</span><span class="n">t</span><span class="p">[</span><span class="n">m</span><span class="o">*</span><span class="n">j</span><span class="p">][</span><span class="n">i</span><span class="o">/</span><span class="n">j</span><span class="p">];</span>
<span class="linenos" data-linenos="61 "></span>        <span class="n">t</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span>
<span class="linenos" data-linenos="62 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="o">/</span><span class="n">m</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="63 "></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;=</span><span class="n">i</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="64 "></span>                <span class="n">t</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">+=</span><span class="n">j</span><span class="o">*</span><span class="p">(</span><span class="n">t</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">j</span><span class="p">]</span><span class="o">+</span><span class="n">c</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">j</span><span class="p">])</span><span class="o">*</span><span class="n">pw</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">*</span><span class="n">t</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">];</span>
<span class="linenos" data-linenos="65 "></span>            <span class="n">t</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">*=</span><span class="n">inv</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="66 "></span>            <span class="n">t</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">/=</span><span class="n">pw</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">];</span>
<span class="linenos" data-linenos="67 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos="68 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos="69 "></span>    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span><span class="n">t</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="n">n</span><span class="p">]</span><span class="o">*</span><span class="p">(</span><span class="n">modint</span><span class="p">(</span><span class="n">n</span><span class="p">)</span><span class="o">^</span><span class="n">k</span><span class="p">));</span>
<span class="linenos" data-linenos="70 "></span><span class="p">}</span>
</code></pre></div>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\P5824.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\P7470.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">题解 P4500 【[ZJOI2018]树】</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-03-29 23:10:37</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/生成函数/" class="tag"><span  style="background-color: rgb(231, 76, 60);">生成函数</span></a>&nbsp;<a href="/tags/题解/" class="tag"><span  style="background-color: rgb(82, 196, 26);">题解</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
